#pragma once
#include"Sort.h"
#include"Stack.h"

void ArrayPrint(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", *(a + i));
	}
	printf("\n");
}

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		int end = i;
		int keyi = a[i + 1];
		while (end >= 0)
		{
			if (a[end] > keyi)
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}
			--end;
		}
		a[end + 1] = keyi;
	}

}

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = (gap / 3) + 1;
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int keyi = a[i + gap];
			while (end >= 0)
			{
				if (a[end] > keyi)
				{
					a[end + gap] = a[end];
				}
				else
				{
					break;
				}
				end -= gap;
			}
			a[end + gap] = keyi;
		}
	}
}


void SelectSort(int* a, int n)
{
	int left = 0, right = n - 1;
	while (left < right)
	{
		int maxi = left, mini = left;
		for (int i = left; i <= right; ++i)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		Swap(&a[left], &a[mini]);
		if (maxi == left)
		{
			maxi = mini;
		}
		Swap(&a[right], &a[maxi]);
		++left;
		--right;
	}
}

void ADJustDownMax(int* a, int n, int parent)
{
	int parents = parent;
	int child = (parents * 2) + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child + 1])
		{
			++child;
		}
		if (a[child] > a[parents])
		{
			Swap(&a[child], &a[parents]);
		}
		parents = child;
		child = (parents * 2) + 1;
	}
}

void HeapSort(int* a, int n)
{
	//建大堆
	for (int i = 0; i < n; ++i)
	{
		ADJustDownMax(a, n, i);
	}

	//开始向下调整-大的数下沉到堆底
	int end = n - 1;
	while (end >= 0)
	{
		Swap(&a[end], &a[0]);
		ADJustDownMax(a, end, 0);
		end--;
	}
}


void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		bool flag = true;
		for (int k = 1; k < n - i; ++k)
		{
			if (a[k - 1] > a[k])
			{
				Swap(&a[k - 1], &a[k]);
				flag = false;
			}
		}
		if (flag)
			break;
	}
}


void QuickSortTest(int* a, int n)
{
	int left = 0, right = n - 1;
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] > a[keyi])
		{
			--right;
		}
		while (left < right && a[left] < a[keyi])
		{
			++left;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[right]);
}


void QuickSort(int* a, int head, int end)
{
	if (head >= end)
		return;

	int left = head, right = end;
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	QuickSort(a, head, left - 1);
	QuickSort(a, right + 1, end);
}



void QuickSortNonR(int* a, int head, int end)
{
	Stack st;
	StackInit(&st);
	StackPush(&st, end);
	StackPush(&st, head);
	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		int l = left;
		StackPop(&st);
		int right = StackTop(&st);
		int r = right;
		StackPop(&st);
		int keyi = left;
		while (left < right)
		{
			while (left < right && a[right] >= a[keyi])
			{
				--right;
			}
			while (left < right && a[left] <= a[keyi])
			{
				++left;
			}
			Swap(&a[left], &a[right]);
		}
		Swap(&a[left], &a[keyi]);
		if (right + 1 < r)
		{
			StackPush(&st, r);
			StackPush(&st, right + 1);
		}
		if (left - 1 > l)
		{
			StackPush(&st, left - 1);
			StackPush(&st, l);
		}
	}
	StackDestroy(&st);
}

int GetMidIndex(int* a, int head, int end)
{
	int mid = (head + end) / 2;
	if (a[head] > a[mid])
	{
		if (a[mid] > a[end])//a[head]>a[mid]>a[end]
		{
			return mid;
		}
		else//a[mid]<a[end]
		{
			if (a[head] > a[end])//a[head]>a[end]>a[mid]
			{
				return end;
			}
			else//a[end]>a[head]>a[mid]
			{
				return head;
			}
		}
	}
	else//a[mid]>a[head]
	{
		if (a[mid] > a[end])
		{
			if (a[head] > a[end])//a[mid]>a[head]>a[end]
			{
				return head;
			}
			else//a[mid]>a[end]>a[head]
			{
				return end;
			}
		}
		else//a[end]>a[mid]>a[head]
		{
			return mid;
		}
	}
}

void QuickSortHole(int* a, int head, int end)
{
	if (head >= end)
		return;

	if ((end - head + 1) <= 15)
	{
		InsertSort(a + head, end - head + 1);
	}
	else
	{
		int left = head, right = end;
		Swap(&a[left], &a[GetMidIndex(a, head, end)]);
		int hole = left;
		int keyi = a[head];
		while (left < right)
		{
			while (left < right && a[right] >= keyi)
			{
				--right;
			}
			a[hole] = a[right];
			hole = right;
			while (left < right && a[left] <= keyi)
			{
				++left;
			}
			a[hole] = a[left];
			hole = left;
		}
		a[hole] = keyi;
		QuickSortHole(a, head, hole - 1);
		QuickSortHole(a, hole + 1, end);
	}
}

void QuickSortDoublePoint(int* a, int head, int end)
{
	if (head >= end)
		return;

	int prev = head;
	int cur = head + 1;
	int keyi = head;
	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		
		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	QuickSortDoublePoint(a, head, prev - 1);
	QuickSortDoublePoint(a, prev+1 , end);
}


void QuickSortMax(int* a, int head, int end)
{
	if (head >= end)
		return;

	if ((end - head + 1) <= 15)
	{
		InsertSort(a + head, end - head + 1);
	}
	else
	{
		int left = head;
		int right = end;
		Swap(&a[left], &a[GetMidIndex(a, head, end)]);
		int keyi = left;
		while (left < right)
		{
			while (left < right && a[right] >= a[keyi])
			{
				--right;
			}
			while (left < right && a[left] <= a[keyi])
			{
				++left;
			}
			Swap(&a[left], &a[right]);
		}
		Swap(&a[left], &a[keyi]);
		QuickSortMax(a, head, left - 1);
		QuickSortMax(a, right + 1, end);
	}
}

int GetRandMidIndex(int* a, int head, int end)
{
	srand((unsigned int)time(NULL));
	int mid = head+rand()%(end-head);
	if (a[head] > a[mid])
	{
		if (a[mid] > a[end])//a[head]>a[mid]>a[end]
		{
			return mid;
		}
		else//a[mid]<a[end]
		{
			if (a[head] > a[end])//a[head]>a[end]>a[mid]
			{
				return end;
			}
			else//a[end]>a[head]>a[mid]
			{
				return head;
			}
		}
	}
	else//a[mid]>a[head]
	{
		if (a[mid] > a[end])
		{
			if (a[head] > a[end])//a[mid]>a[head]>a[end]
			{
				return head;
			}
			else//a[mid]>a[end]>a[head]
			{
				return end;
			}
		}
		else//a[end]>a[mid]>a[head]
		{
			return mid;
		}
	}
}

void QuickSortMaxDup(int* a, int head, int end)
{
	if (head >= end)
		return;

	if ((end - head + 1) <= 12)
	{
		InsertSort(a + head, end - head + 1);
	}
	else
	{
		int left = head;
		int right = end;
		int cur = left + 1;
		Swap(&a[left], &a[GetRandMidIndex(a, head, end)]);
		int keyi = a[left];
		while (cur <= right)
		{
			if (a[cur] < keyi)
			{
				Swap(&a[cur++], &a[left++]);
			}
			else if (a[cur] > keyi)
			{
				Swap(&a[cur], &a[right--]);
			}
			else if (a[cur] == keyi)
			{
				++cur;
			}
		}
		QuickSortMaxDup(a, head, left - 1);
		QuickSortMaxDup(a, right + 1, end);
	}
}

void MergeSort(int* a, int* tmp, int head, int end)
{
	if (head >= end)
		return;
	int mid = (head + end) / 2;

	MergeSort(a, tmp, head, mid);
	MergeSort(a, tmp, mid+1, end);

	int left1 = head,right1 = mid;
	int left2 = mid + 1, right2 = end;
	int i = head;
	while (left1 <= right1 && left2 <= right2)
	{
		if (a[left1] < a[left2])
		{
			tmp[i++] = a[left1++];
		}
		else
		{
			tmp[i++] = a[left2++];
		}
	}
	while (left1 <= right1)
	{
		tmp[i++] = a[left1++];
	}
	while (left2 <= right2)
	{
		tmp[i++] = a[left2++];
	}
	memcpy(a + head, tmp + head, sizeof(int) * (end - head + 1));

}


void MergeSortNonR1(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (!tmp)
		exit(EOF);

	int rangeN = 1;
	while (rangeN < n)
	{
		for (int i = 0; i < n; i += 2 * rangeN)
		{
			int left1 = i, right1 = i + rangeN - 1;
			int left2 = i + rangeN, right2 = i + 2 * rangeN - 1;
			int k = i;
			if (right1 >= n)
			{
				break;
			}
			else if (left2 >= n)
			{
				break;
			}
			else if (right2 >= n)
			{
				right2 = n - 1;
			}

			while (left1 <= right1 && left2 <= right2)
			{
				if (a[left1] < a[left2])
				{
					tmp[k++] = a[left1++];
				}
				else
				{
					tmp[k++] = a[left2++];
				}
			}
			while (left1 <= right1)
			{
				tmp[k++] = a[left1++];
			}
			while (left2 <= right2)
			{
				tmp[k++] = a[left2++];
			}
			memcpy(a + i, tmp + i, sizeof(int) * (right2-i+1));
		}
		rangeN *= 2;
	}
}


void MergeSortNonR2(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (!tmp)
		exit(EOF);

	int rangeN = 1;
	while (rangeN < n)
	{
		for (int i = 0; i < n; i += 2 * rangeN)
		{
			int left1 = i, right1 = i + rangeN - 1;
			int left2 = i + rangeN, right2 = i + 2 * rangeN - 1;
			int k = i;
			if (right1 >= n)
			{
				right1 = n - 1;

				left2 = n;
				right2 = n - 1;
			}
			else if (left2 >= n)
			{
				left2 = n;
				right2 = n - 1;
			}
			else if (right2 >= n)
			{
				right2 = n - 1;
			}

			while (left1 <= right1 && left2 <= right2)
			{
				if (a[left1] < a[left2])
				{
					tmp[k++] = a[left1++];
				}
				else
				{
					tmp[k++] = a[left2++];
				}
			}
			while (left1 <= right1)
			{
				tmp[k++] = a[left1++];
			}
			while (left2 <= right2)
			{
				tmp[k++] = a[left2++];
			}
		}
		memcpy(a, tmp, sizeof(int) * n);
		rangeN *= 2;
	}
}


void CountSort(int* a, int n)
{
	int maxi = a[0], mini = a[0];
	for (int i = 0; i < n; ++i)
	{
		if (a[i] > maxi)
		{
			maxi = a[i];
		}
		if (a[i] < mini)
		{
			mini = a[i];
		}
	}
	int range = maxi - mini + 1;
	int* tmp = (int*)calloc(range, sizeof(int));
	if (!tmp)
		exit(EOF);

	for (int i = 0; i < n; ++i)
	{
		tmp[a[i] - mini]++;
	}

	for (int i = 0, k = 0; i < range; ++i)
	{
		while (tmp[i]--)
		{
			a[k++] = i + mini;
		}
	}
}